<?php

/*
 * Finding a longest subsequence in a series of integers.
 * Notice that subsequence is not a substring!!!
 */

require_once 'util.php';

$sample = generateRandomArray(0, 10, 10);

var_dump($sample);

$result = longestIncreasingSubsequence($sample);

var_dump($result);

function longestIncreasingSubsequence( $sample ){
	$ret = array();
	$length = count( $sample );
	if( $length<=0 ){
			return $ret;
	}

	if( 1 == $length ){
		$ret[] = $sample[0];
		return $ret;
	}

	// Array of longest increasing subsequence
	$L = array_fill(0, $length, 1);

	// Array of predecessors in the subsequence
	$P = array_fill(0, $length, 0);

	$longest = 0;
	$position = 0;

	for( $i=0; $i<$length; $i++ ){
		for( $j=0; $j<$i; $j++ ){
			if( $sample[$i] > $sample[$j] ){
				// Can append to the subsequence ending at $j
				// Update data at $i if this is longer than the current record
				if( $L[$j] + 1 > $L[$i] ){
					$L[$i] = $L[$j] + 1;
					$P[$i] = $j;
				}
			}
		}

		if( $L[$i] > $longest ){
			$longest = $L[$i];
			$position = $i;
		}
	}

	var_dump( $L );
	var_dump( $P );

	$cur = $position;
	for( $index=0; $index<$longest; $index++ ){
		array_unshift($ret, $sample[$cur]);
		$cur = $P[$cur];
	}

	//array_reverse($ret);

	return $ret;
}

?>